0% completed
Little-o (o) and Little-omega (ω) Notations provide more precise ways to describe the growth rate of functions. While Big-O and Big-Omega set upper and lower bounds that an algorithm’s complexity can approach, little-o and little-omega are stricter. They define cases where a function grows strictly slower (little-o) or strictly faster (little-omega) than another.
Little-o Notation (o-notation)
Little-o notation, represented as
Formal Definition
A function
for all
- Interpretation:
grows slower than any constant multiple of as .
Example of Little-o
Let’s say
- For any constant
, will eventually be less than as gets large. - Therefore,
, since grows slower than .
In this case,
Little-omega Notation (ω-notation)
Little-omega notation, represented as
Formal Definition
A function
for all
- Interpretation:
grows faster than any constant multiple of as .
Example of Little-omega
Consider
- For any constant
, will eventually exceed as becomes large. - Therefore,
, indicating that grows strictly faster than .
In this case,
Key Points to Remember
- Little-o and Little-omega Are Stricter Notations: They define functions that grow slower or faster without approaching the growth rate of the comparison function.
- Strict Growth Conditions: These notations require that
strictly remains slower or faster than for large input sizes. - Useful for Precise Analysis: While Big-O and Big-Omega are broad, little-o and little-omega provide clarity for strictly different growth rates.
On this page
Little-o Notation (o-notation)
Formal Definition
Example of Little-o
Little-omega Notation (ω-notation)
Formal Definition
Example of Little-omega
Key Points to Remember